//
// Created by ki on 2021/3/5.
//

/*
 * 斐波那契数列来浅谈矩阵快速幂
 */
#include <iostream>

using namespace std;

int quickPow(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1) ans *= a;
        a = a*a;
        b >>= 1;
    }
    return ans;
}

int pow(int a, int b)
{
    int ans = 1;
    for (int i=0; i<b; i++)
    {
        ans *= a;
    }
    return ans;
}

int n;

struct matrix
{
    long long x[105][105]{};
};

matrix multiply(matrix &a, matrix &b)
{
    matrix c;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            for (int k=1; k<=n; k++)
            {
                c.x[i][j] += a.x[i][k] + b.x[k][j];
            }
        }
    }
    return c;
}

matrix mPow(matrix &a, int b) //矩阵a的b次方
{
    matrix ans;
    for (int i=1; i<=n; i++)
    {
        ans.x[i][i] = 1; //单位矩阵
    }
    while (b)
    {
        if (b & 1) ans = multiply(ans, a);
        a = multiply(a,a);
        b >>= 1;
    }
    return ans;
}

